package com.desheng.bigdata.ds.tree;

import com.desheng.bigdata.ds.queue.Queue;

/**
 * 自定义一个二叉树
 * 使用非递归的方式遍历树
 * 需要使用到栈结构
 */
public class BinaryXTree<K extends Comparable<K>, V> {

    public class Node<K, V> {
        Node<K, V> left;
        K key;
        V data;
        Node<K, V> right;
        public Node(Node<K, V> left, K key, V data, Node<K, V> right) {
            this.left = left;
            this.key = key;
            this.data = data;
            this.right = right;
        }
    }

    private int size;

    private Node<K, V> root;

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void insert(K key, V data) {
        root = insert(root, key, data);
    }

    private Node<K, V> insert(Node<K, V> node, K key, V data) {
        if(node == null) {
            size++;
            return new Node<>(null, key, data, null);
        }
        //节点不为null，就需要和key进行比较，三个结果
        int compared = node.key.compareTo(key);
        if(compared > 0) {//node的key小于key 插入左子树
            node.left = insert(node.left, key, data);
        } else if(compared < 0) {//node的key大于key 插入右子树
            node.right = insert(node.right, key, data);
        } else {//更新当前节点
            size++;
            node.data = data;
        }
        return node;
    }
    public V get(K key) {
        return get(root, key);
    }

    private V get(Node<K, V> node, K key) {
        if(node == null) {
            return null;
        }
        int compared = node.key.compareTo(key);
        if(compared > 0) {//node的key小于key 插入左子树
            return get(node.left, key);
        } else if(compared < 0) {//node的key大于key 插入右子树
            return get(node.right, key);
        } else {//更新当前节点
            return node.data;
        }
    }

    public void delete(K key) {
        delete(root, key);
    }

    private Node<K, V> delete(Node<K, V> node, K key) {
        //node为null
        if(node == null) {
            return null;
        }
        //node不为null
        int compared = node.key.compareTo(key);
        if(compared > 0) {//node的key小于key 插入左子树
            node.left = delete(node.left, key);
        } else if(compared < 0) {//node的key大于key 插入右子树
            node.right = delete(node.right, key);
        } else {//当前节点
            size--;
            if(node.right == null) {
                return node.left;
            }
            if(node.left == null) {
                return node.right;
            }
            Node minNode = node.right;
            while (minNode.left != null) {
                minNode = minNode.left;
            }
            //删除右子树中得最小节点
            Node<K, V> n = node.right;
            while (n.left != null) {
                if(n.left.left == null) {
                    n.left = null;
                } else {
                    n = n.left;
                }
            }
            //让node节点的左子树成为minNode的左子树
            minNode.left = node.left;
            //让node节点的右子树成为minNode的右子树
            minNode.right = node.right;
            //让node的父节点指向minNode
            node = minNode;
        }
        return node;
    }

    public K minKey(){
        return min(root).key;
    }
    private Node<K, V> min(Node<K, V> node) {
        if(node.left != null) {
            return min(node.left);
        } else {
            return node;
        }
    }

    public K maxKey() {
        return max(root).key;
    }

    private Node<K, V> max(Node<K, V> node) {
        if(node.right != null) {
            return max(node.right);
        } else {
            return node;
        }
    }

    public void prevOrder() {
        prevOrder(root);
    }
    /**
     * 前序遍历：中-->左-->右
     */
    private void prevOrder(Node<K, V> node) {
        System.out.print(node.key + "-->");
        if(node.left != null) {
            prevOrder(node.left);
        }
        if(node.right != null) {
            prevOrder(node.right);
        }
    }

    public void midOrder() {
        midOrder(root);
    }
    /**
     * 中序遍历：左-->中-->右
     */
    private void midOrder(Node<K, V> node) {
        if(node.left != null) {
            midOrder(node.left);
        }
        System.out.print(node.key + "-->");
        if(node.right != null) {
            midOrder(node.right);
        }
    }

    public void postOrder() {
        postOrder(root);
    }

    /**
     * 后序遍历：左-->右-->中
     */
    private void postOrder(Node<K, V> node) {
        if(node.left != null) {
            postOrder(node.left);
        }
        if(node.right != null) {
            postOrder(node.right);
        }
        System.out.print(node.key + "-->");
    }

    //层序遍历
    public void layerOrder(){
        Queue<Node<K, V>> nodes = new Queue<>();
        nodes.enqueue(root);
        while (!nodes.isEmpty()) {
            Node<K, V> node = nodes.dequeue();
            System.out.print(node.key+ "-->");
            if(node.left != null) {
                nodes.enqueue(node.left);
            }
            if(node.right != null) {
                nodes.enqueue(node.right);
            }
        }
    }


    public int maxDepth(){
        return maxDepth(root);
    }

    private int maxDepth(Node<K, V> node) {
        if(node == null) {
            return 0;
        }
        int maxL = 0;
        if(node.left != null) {
            maxL = maxDepth(node.left);
        }
        int maxR = 0;
        if(node.right != null) {
            maxR = maxDepth(node.right);
        }
        return 1 + (maxL > maxR ? maxL : maxR);
    }
}
